/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/submissions/567140898/
 * 300. 最长递增子序列
 * medium 李佳颖 2024.09.06
 * 经典线性
 */

 class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int>ldp(n,1);
        for (int i=1;i<n;i++)
            for (int j=0;j<i; j++)  
                if (nums[j]<nums[i])
                    ldp[i]=max(ldp[j]+1,ldp[i]);
        return *max_element(ldp.begin(), ldp.end());
    }
};